{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# TinySMPC Tutorial\n",
    "\n",
    "This tutorial runs through the basics of secure multi-party computation, using TinySMPC.\n",
    "\n",
    "[Secure multi-party computation](https://en.wikipedia.org/wiki/Secure_multi-party_computation) (SMPC) is a cryptographic technique that allows multiple people to compute a function, where the function itself and its outputs are public, but the inputs are kept private to each person.\n",
    "\n",
    "A simple example: a group of friends want to compute the total money owned by the group, but without revealing any individual's bank balance."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Setup\n",
    "\n",
    "Let's import the only three classes we'll need from TinySMPC.\n",
    "\n",
    "TinySMPC is written in vanilla Python for understandability, so we don't need any external modules!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from tinysmpc import VirtualMachine, PrivateScalar, SharedScalar"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Creating Multiple Machines\n",
    "\n",
    "First, let's create a few `VirtualMachines`.\n",
    "\n",
    "A `VirtualMachine` represents the private computer of a user, and contains data that should not be revealed to other users."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "alice = VirtualMachine('alice')\n",
    "bob = VirtualMachine('bob')\n",
    "charlie = VirtualMachine('charlie')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Think of Alice, Bob, and Charlie as completely separate computers that can communicate over some network.\n",
    "\n",
    "(For simplicity, `VirtualMachines` are simulated and all run locally in this notebook kernel.) \n",
    "\n",
    "Next, let's create private data on each computer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Generating Private Data\n",
    "\n",
    "Private data on a computer is represented in a `PrivateScalar` object. Think of these numbers as each person's bank balance."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = PrivateScalar(40000, alice)\n",
    "b = PrivateScalar(15000, bob)\n",
    "c = PrivateScalar(-20000, charlie)  # Charlie is heavily in debt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Alice can only see her own balance, and cannot see Bob and Charlie's balances.\n",
    "\n",
    "We can confirm this by looking at the contents of Alice's computer. (Just print `alice`!)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "VirtualMachine('alice')\n",
       " - PrivateScalar(40000, 'alice')"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "alice"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we can see, Alice's computer only contains her own `PrivateScalar` that represents her salary.\n",
    "\n",
    "This is the same for Bob and Charlie's computers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "VirtualMachine('bob')\n",
       " - PrivateScalar(15000, 'bob')"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bob"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "VirtualMachine('charlie')\n",
       " - PrivateScalar(-20000, 'charlie')"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "charlie"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, let's see how we can compute a public function over these private values."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Secret Sharing\n",
    "\n",
    "Let's say Alice, Bob, and Charlie want to compute the sum of their bank balances, without revealing their individual balances to anyone.\n",
    "\n",
    "This is exactly what secure multi-party computation (SMPC) is made for. A technique called \"secret sharing\" is the fundamental building block of [most](https://crypto.stackexchange.com/questions/80764/is-there-a-secure-multi-party-computation-smpc-scheme-that-doesnt-use-secret) SMPC schemes, so let's talk about that first.\n",
    "\n",
    "To perform secret sharing, we just call `.share()` on a `PrivateScalar`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "SharedScalar\n",
       " - Share(7518107586050012064, 'alice', Q=None)\n",
       " - Share(-4113260924413135564, 'bob', Q=None)\n",
       " - Share(-3404846661636836500, 'charlie', Q=None)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "shared_a = a.share([alice, bob, charlie])\n",
    "shared_a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What just happened? \n",
    "\n",
    "First, TinySMPC used a technique called additive secret sharing to generate three encrypted \"shares\" of `a`. As you can see above, each share looks like a random number, and it's indeed impossible to find out the true value of `a` from any share (or any two shares).\n",
    "\n",
    "Then, we sent one encrypted share to each computer. If we look at Bob's machine, he now owns a new `Share` object (that Alice sent him)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "VirtualMachine('bob')\n",
       " - PrivateScalar(15000, 'bob')\n",
       " - Share(-4113260924413135564, 'bob', Q=None)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bob"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "All of the shares that correspond to the original value `a` are tracked in a `SharedScalar` object, which is `shared_a` here. \n",
    "\n",
    "Reconstructing the value `a` requires bringing all three shares from Alice, Bob, and Charlie.\n",
    "\n",
    "We can do this easily by calling `.reconstruct()` on a `SharedScalar`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "PrivateScalar(40000, 'alice')"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "shared_a.reconstruct(alice)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Behind the scenes, TinySMPC sent all shares to Alice, and then reconstructed the original value of `a`. It's the opposite of `.share()`.\n",
    "\n",
    "Now we know how to use additive secret sharing. But this isn't very useful by itself, so let's look at how to do computation with the shares next.\n",
    "\n",
    "(If you're curious about how we generate and reconstruct shares, check out [secret_sharing.py](https://github.com/kennysong/tinysmpc/blob/master/tinysmpc/secret_sharing.py).)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Basic Computation\n",
    "\n",
    "A magical property of the additive secret sharing scheme is that we can do arithmetic directly on the encrypted shares!\n",
    "\n",
    "This enables the \"computation\" in secure multi-party computation.\n",
    "\n",
    "Let's try doing addition on an encrypted `SharedScalar`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "PrivateScalar(45000, 'alice')"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "shared_a = a.share([alice, bob, charlie])\n",
    "shared_a = shared_a + 5000\n",
    "shared_a.reconstruct(alice)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It worked! Note that we added `5000` directly to the encrypted `SharedScalar`, and it decrypts to the same number as if we added `5000` directly to the original value.\n",
    "\n",
    "To do this, we applied a special arithmetic protocol directly on each share. For fun, let's inspect the share values directly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Shares before adding 5000:\n",
      "SharedScalar\n",
      " - Share(-575460379469600407, 'alice', Q=None)\n",
      " - Share(5455160774533057975, 'bob', Q=None)\n",
      " - Share(-4879700395063417568, 'charlie', Q=None)\n",
      "\n",
      "Shares after adding 5000:\n",
      "SharedScalar\n",
      " - Share(-575460379469595407, 'alice', Q=None)\n",
      " - Share(5455160774533057975, 'bob', Q=None)\n",
      " - Share(-4879700395063417568, 'charlie', Q=None)\n"
     ]
    }
   ],
   "source": [
    "shared_a = a.share([alice, bob, charlie])\n",
    "print('Shares before adding 5000:')\n",
    "print(shared_a)\n",
    "\n",
    "shared_a = shared_a + 5000\n",
    "print('\\nShares after adding 5000:')\n",
    "print(shared_a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you stare long enough, you'll see that we added `5000` directly to the first share's encrypted value. This is pretty simple (it's not always this easy), and you can see the implementation at [shared_addition.py](/tinysmpc/shared_addition.py).\n",
    "\n",
    "On top of doing addition between a `SharedScalar` and a (public) integer, we can also do addition between `SharedScalars`.\n",
    "\n",
    "This is how we can securely compute the sum of everyone's bank balances."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "PrivateScalar(35000, 'bob')"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "shared_a = a.share([alice, bob, charlie])\n",
    "shared_b = b.share([alice, bob, charlie])\n",
    "shared_c = c.share([alice, bob, charlie])\n",
    "\n",
    "shared_sum = shared_a + shared_b + shared_c\n",
    "shared_sum.reconstruct(bob)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here, we computed the total sum of money owned by everyone, and sent the resulting sum to Bob (who can then share the sum \"publicly\").\n",
    "\n",
    "The addition happened directly between encrypted `SharedScalars`, without anyone seeing anyone else's secret values!\n",
    "\n",
    "Next, let's see how to do more advanced computations (e.g. multiplication, comparison, floating point numbers)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Advanced Computation\n",
    "\n",
    "Addition is fun, but we can compute much more complex functions with SMPC as well."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Multiplication\n",
    "\n",
    "Let's try out multiplication:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "PrivateScalar(-100, 'alice')"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "shared_a = PrivateScalar(5, alice).share([alice, bob])\n",
    "shared_b = PrivateScalar(-10, bob).share([alice, bob])\n",
    "\n",
    "shared_prod = 2 * shared_b * shared_a\n",
    "shared_prod.reconstruct(alice)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exponentiation\n",
    "\n",
    "Exponentiation works as well (with a public integer in the exponent):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "PrivateScalar(10000, 'alice')\n",
      "PrivateScalar(-1000000, 'bob')\n"
     ]
    }
   ],
   "source": [
    "shared_exp1 = shared_prod ** 2\n",
    "shared_exp2 = shared_prod ** 3\n",
    "\n",
    "print(shared_exp1.reconstruct(alice))\n",
    "print(shared_exp2.reconstruct(bob))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Comparison\n",
    "\n",
    "You can also do comparison against a public integer:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "PrivateScalar(1, 'p2')\n",
      "PrivateScalar(0, 'p2')\n"
     ]
    }
   ],
   "source": [
    "print(shared_exp1 > 9999)\n",
    "print(shared_exp2 > -999999)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(Note: due to the details of the SecureNN comparison algorithm used here, the output of a comparison is a boolean `PrivateScalar` on an ephemeral `VirtualMachine`. You can get the boolean value by accessing `.value`. To see how it works, see [shared_comparison.py](https://github.com/kennysong/tinysmpc/blob/master/tinysmpc/shared_comparison.py).)\n",
    "\n",
    "We could potentially use this to implement a ReLU function on `SharedScalars`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "PrivateScalar(10, 'alice')\n",
      "PrivateScalar(0, 'alice')\n"
     ]
    }
   ],
   "source": [
    "def relu(shared_x):\n",
    "    if (shared_x > 0).value: \n",
    "        return shared_x\n",
    "    return 0 * shared_x\n",
    "\n",
    "shared_x = PrivateScalar(10, alice).share([alice, bob])\n",
    "\n",
    "shared_relu_x = relu(shared_x)\n",
    "shared_relu_neg_x = relu(-1 * shared_x)\n",
    "\n",
    "print(shared_relu_x.reconstruct(alice))\n",
    "print(shared_relu_neg_x.reconstruct(alice))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Floating Point Numbers\n",
    "\n",
    "Last, it's likely that in real-life applications, we'd want to use SMPC on floating point numbers. This is possible!\n",
    "\n",
    "Recall that our `SharedScalar` and additive secret sharing in general only works on integers, so we need to convert floating point numbers into a fixed-point integer representation first.\n",
    "\n",
    "Let's see how to do this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "from tinysmpc.fixed_point import fixed_point, float_point"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(500000, 50000, 5, -5)"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fixed_point(0.005), fixed_point(0.0005), fixed_point(0.00000005), fixed_point(-0.00000005)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can likely see, TinySMPC uses an incredibly simple fixed-point representation. We map floats to integers by multiplying by `10^8`, which preserves `8` decimal places of precision.\n",
    "\n",
    "To get the floating point number back, just use `float_point()`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.005, 0.0005, 5e-08, -5e-08)"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "float_point(500000), float_point(50000), float_point(5), float_point(-5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's see this in action:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(44.44355556, 44.44355556)"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = fixed_point(1.2345)\n",
    "b = fixed_point(-5.4321)\n",
    "\n",
    "shared_a = PrivateScalar(a, alice).share([alice, bob])\n",
    "shared_b = PrivateScalar(b, bob).share([alice, bob])\n",
    "\n",
    "true_res = (-5.4321 - 1.2345) ** 2\n",
    "shared_res = (shared_b - shared_a) ** 2\n",
    "res = shared_res.reconstruct(alice)\n",
    "res = float_point(res.value, n_mults=1)\n",
    "\n",
    "res, true_res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It works! \n",
    "\n",
    "A big disclaimer: fixed-point encoding is finnicky to work with, as you can tell from the unexplained `n_mults` parameter. You'll likely see incorrect results if you don't carefully account for conversion factors and overflows. \n",
    "\n",
    "Any good, production SMPC library will **transparently** convert and handle floats for you. This adds a lot of codebase complexity, though, and to keep the source code of TinySMPC simple and readable, I decided against implementing this. \n",
    "\n",
    "However, now you understand the core concept of how SMPC can work on floats!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Arbitrary Functions\n",
    "\n",
    "With these tools, we can compute more complex functions as well. For example, we could compute the `exp()` function using its Taylor series.\n",
    "\n",
    "I'll leave this as an exercise for the reader."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Limitations\n",
    "\n",
    "TinySMPC is not intended to be a production SMPC library, so it leaves out several important features. \n",
    "\n",
    " - Division of `SharedScalars`. This is possible, but complex to implement (see Algorithm 8 of [the SecureNN paper](https://eprint.iacr.org/2018/442.pdf)).\n",
    " - Comparison of `SharedScalars`. Also possible, but complex to implement.\n",
    " - `SharedScalars` do not transparently handle floating point numbers.\n",
    " - Lack of vectorization, lack of a math library, etc.\n",
    "\n",
    "We should also talk about the limitations of SMPC in general as a protocol.\n",
    "\n",
    "- It assumes all participants will honestly apply the right local computations – it's trivial to alter the value of the outcome if you wanted to. This is sometimes called the \"[honest-but-curious](https://crypto.stanford.edu/pbc/notes/crypto/sfe.html)\" assumption. There are [extensions to SMPC](https://mortendahl.github.io/2017/08/13/secret-sharing-part3/) that provide integrity.\n",
    "- It requires all participants to stay online. If one machine fails, we cannot continue to compute or decrypt. There are also extensions that solve this problem (search for \"k-out-of-n secret sharing\").\n",
    "- It's as slow as your network! A single multiplication requires several round-trip messages between all computers. We'd ideally like the machines to be colocated on a fast local network, but many real-world use cases of SMPC have machines separated over the public internet. SMPC algorithms are often evaluated based on the amount of communication required."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Recap\n",
    "\n",
    "To recap, SMPC allows multiple people to compute a function, where the function itself and its outputs are public, but the inputs are kept private to each person.\n",
    "\n",
    "TinySMPC implements the core building blocks of generating encrypted secret shares, and doing computations directly on that encrypted data.\n",
    "\n",
    "Here's a summary of the encrypted operations that TinySMPC provides.\n",
    "\n",
    "|                    | Supported?              | Implementation                                                                          |\n",
    "|--------------------|-------------------------|-----------------------------------------------------------------------------------------|\n",
    "| **Addition**       | ✅                       | [SPDZ](https://eprint.iacr.org/2011/535.pdf) algorithm. <br/> See [shared_addition.py](https://github.com/kennysong/tinysmpc/blob/master/tinysmpc/shared_addition.py)             |\n",
    "| **Subtraction**    | ✅                       | In terms of addition and multiplication.                                                 |\n",
    "| **Multiplication** | ✅                       | [SPDZ](https://eprint.iacr.org/2011/535.pdf) algorithm.  <br/> See [shared_multiplication.py](https://github.com/kennysong/tinysmpc/blob/master/tinysmpc/shared_multiplication.py) |\n",
    "| **Division**       | ❌ (too complicated)     | Possible with [SecureNN](https://eprint.iacr.org/2018/442.pdf).                                                                                       |\n",
    "| **Exponentiation**       | ✅ (public integer only)     | In terms of multiplication.                                                                                       |\n",
    "| **Greater Than**   | ✅ (public integer only) | [SecureNN](https://eprint.iacr.org/2018/442.pdf) algorithm. <br/> See [shared_comparison.py](https://github.com/kennysong/tinysmpc/blob/master/tinysmpc/shared_comparison.py)     |\n",
    "\n",
    "What's next?\n",
    "\n",
    "This was a high-level tutorial. If you want to understand how these protocols work behind the scenes, I encourage you to check out the [source code of TinySMPC](https://github.com/kennysong/tinysmpc)! It was written to be as small and understandable as possible, using vanilla Python and no extra modules.\n",
    "\n",
    "If you want to use SMPC in production, especially for machine learning, I'd recommend looking at [PySyft](https://github.com/OpenMined/PySyft/) and [TF Encrypted](https://github.com/tf-encrypted/tf-encrypted). They implement useful features such as: vectorization / tensorization, high-level math and ML APIs, transparent float conversion, and more. "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
